package com.leetcode.partition1;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/10/5 9:41
 */
public class LC85最大矩形 {

    public static int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0) return 0;
        return dynamicProgramming(matrix);
    }

    public static void main(String[] args) {
//        char[][] matrix = {
//                {'1', '0', '1', '0', '0'},
//                {'1', '0', '1', '1', '1'},
//                {'1', '1', '1', '1', '1'},
//                {'1', '0', '0', '1', '0'}
//        };
        char[][] matrix = {
                {'0', '0', '0', '0', '0', '0', '1'},
                {'0', '0', '0', '0', '1', '1', '1'},
                {'1', '1', '1', '1', '1', '1', '1'},
                {'0', '0', '0', '1', '1', '1', '1'}
        };
        System.out.println(maximalRectangle(matrix));
    }

    private static int dynamicProgramming(char[][] matrix) {
        //dp[i][j][0]表示连续的长，dp[i][j][1]表示连续的宽
        int[][][] dp = new int[matrix.length + 1][matrix[0].length + 1][2];
        int answer = 0;
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if (matrix[i - 1][j - 1] == '0') continue;
                dp[i][j][0] = dp[i][j - 1][0] + 1;
                dp[i][j][1] = dp[i - 1][j][1] + 1;
                //length记录当前位置的矩形能够得到的长
                int length = dp[i][j][0];
                //因为要构成矩形，在根据宽遍历记录时需要取最小的长，并尝试每次加大宽度
                for (int width = 1; width <= dp[i][j][1]; width++) {
                    length = Math.min(length, dp[i - width + 1][j][0]);
                    answer = Math.max(answer, length * width);
                    System.out.println("length=" + length + ", width=" + width);
                }
            }
        }
        Arrays.stream(dp).forEach(val -> {
            for (int[] v : val) {
                System.out.printf("(%d, %d)   ", v[0], v[1]);
            }
            System.out.println();
        });
        return answer;
    }
}
